#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
	vector<int> maxSlidingWindow(vector<int>& nums, int k) {
		vector<int> res; deque<int> aux;
		for (int i = 0, len = k; i < len; i++) {
			while (!aux.empty() && nums[aux.back()] <= nums[i])
				aux.pop_back();
			aux.emplace_back(i);
		}
		res.emplace_back(nums[aux.front()]);

		for (int i = k, len = nums.size(); i < len; i++) {
			while (!aux.empty() && aux.front() <= i - k)
				aux.pop_front();
			while (!aux.empty() && nums[aux.back()] <= nums[i])
				aux.pop_back();
			aux.emplace_back(i);

			res.emplace_back(nums[aux.front()]);
		}
		return res;
	}

private:
};

int main()
{
	Solution solution;
	return 0;
}
